已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1,⋯,A*N−1的中位数指*A(N−1)/2的值,即第⌊(N+1)/2⌋个数(A0为第1个数)。
输入格式:
输入分三行。第一行给出序列的公共长度N(0<N≤100000),随后每行输入一个序列的信息,即N个非降序排列的整数。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的并集序列的中位数。
输入样例1:
输出样例1:
输入样例2:
1 2 3
| 6 -100 -10 1 1 1 1 -50 0 2 3 4 5
|
输出样例2:
思路
最直接的方法就是将给定的2*n个数存入数组中,对数组排序,排序复杂度为O(nlogn)
但是这样就没有利用题目所说的两个给定数组均有序的特点
我们可以将两个有序数组合并成一个仍然有序数组,然后取中间的值即可,合并两有序数组方法为:
- 不断取出两数组中较小的数存入新数组,直到两数组为空(具体看代码)
这样时间复杂度可以是O(n),相当于遍历一遍两个数组
知识点:两有序数组的合并
代码
如下为合并方法,时间复杂度O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| #include <iostream> #include <vector>
using namespace std;
int main() { int n; cin >> n; vector<int> ve1, ve2; for(int i = 1; i <= n; i++) { int id; cin >> id; ve1.push_back(id); } for(int i = 1; i <= n; i++) { int id; cin >> id; ve2.push_back(id); } int a = 0, b = 0; vector<int> ret; while(a < n && b < n) { if(ve1[a] < ve2[b]) { ret.push_back(ve1[a]); a++; } else { ret.push_back(ve2[b]); b++; } } while(a < n) { ret.push_back(ve1[a]); a++; } while(b < n) { ret.push_back(ve2[b]); b++; } cout << ret[(ret.size() - 1) / 2] << endl; return 0; }
|
如下为排序方法,时间复杂度O(nlogn),也可通过,不会超时
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| #include <iostream> #include <algorithm> #include <vector>
using namespace std;
int main() { int n; cin >> n; vector<int> ve; for(int i = 1; i <= n; i++) { int id; cin >> id; ve.push_back(id); } for(int i = 1; i <= n; i++) { int id; cin >> id; ve.push_back(id); } sort(ve.begin(), ve.end()); cout << ve[(2 * n - 1) / 2] << endl; return 0; }
|